package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1648. 销售价值减少的颜色球
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/8 11:52
 */
public class MaxProfit1648 {


    public static void main(String[] args) {
        MaxProfit1648 test = new MaxProfit1648();

        // 14
//        int[] arr = {2, 5};
//        int n = 4;

        // 19
//        int[] arr = {3,5};
//        int n = 6;

        // 110
//        int[] arr = {2,8,4,10,6};
//        int n = 20;

        // 21
//        int[] arr = {1000000000};
//        int n = 1000000000;

        // 373219333
        int[] arr = {497978859,167261111,483575207,591815159};
        int n = 836556809;

        // 525803723
//        int[] arr = {701695700,915736894,35093938,364836059,452183894,951826038,861556610,
//                441929847,842650446,858413011,457896886,35119509,
//                776620034,396643588,83585103,681609037};
//        int n = 598226067;

        // 2410
//        int[] arr = {90,24,49,18,88,50,88,84,48,51,85,84,53,61,60,90,33,41,75,22,43,32,20,87,1,34,36,58,92,93,52,18,
//                41,79,17,46,12,31,62,58,67,3,60,76,62,87,10,81,70,10,23,64,13,29,4,66,62,73,48,29,21,13,24,61,28,44,
//                28,91,79,79,99,95,40,27,60,35,19,89,33};
//        int n = 26;

        int i = test.maxProfit(arr, n);
        System.out.println(i);
    }

    public int maxProfit(int[] inventory, int orders) {
        int end = 0;
        for (int i : inventory) {
            end = Math.max(end, i);
        }
        int st = 0;
        while (st <= end) {
            long m = st + ((end - st) >> 1);
            int count = 0;
            long sum = 0;
            long all = 0;
            for (int i : inventory) {
                if (i > m) {
                    sum =  (sum + ((m + 1 + i) * (i - m) >> 1)) % 1000000007;
                    all += (i - m);
                    count++;
                } else if(i == m) {
                    count++;
                }
            }
            if (all == orders) {
                return (int) sum;
            } else if (all < orders && all + count >= orders) {
               return (int) (( sum + ((orders - all) * m) ) % 1000000007);
            }
            if (all < orders) {
                end = (int) (m - 1);
            } else {
                st = (int) (m + 1);
            }
        }
        return 0;
    }

}
